#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string>vis;
        unordered_set<string>hashi(bank.begin(), bank.end());
        string ch = "ACGT";
        int ret = 0;
        queue<string>q;
        if (!hashi.count(endGene)) return -1;
        if (startGene == endGene) return 0;
        q.push(startGene);
        vis.insert(startGene);
        while (q.size())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                string tmp = q.front();
                q.pop();
                for (int i = 0; i < 8; i++)
                {
                    string cp = tmp;
                    for (int j = 0; j < 4; j++)
                    {
                        cp[i] = ch[j];
                        if (hashi.count(cp) && !vis.count(cp))
                        {
                            if (cp == endGene) return ret;
                            q.push(cp);
                            vis.insert(cp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};